package leetcode;

public class Test1287 {
    public int findSpecialInteger(int[] arr) {
        //方法1：计数
//        int[] bucket=new int[100001];
//
//        for(int i=0;i<arr.length;i++){
//            bucket[arr[i]]++;
//            if(bucket[arr[i]]>arr.length/4)
//                return bucket[arr[i]];
//        }
//        return -1;
        //方法2：使用滑动窗口，窗口大小刚好为1/4+1 窗口两边如果刚好相等，则返回
        int count=arr.length/4; //窗口长度
        for(int i=0;i<arr.length-count;i++){
            if(arr[i+count]==arr[i]){
                return arr[i];
            }
        }
        return -1;
        //方法3：二分查找法
        //分段：以count为一段，把数组切为8段，连续两段出现的数则为结果

    }
}
